Getting the element count in a skip list

Hello,

Is there a simple way to get the number of element in a skip list other than iterating through it and counting them.

I tried the following:

Skip s = create
    Skip s = create
        print "=> " (sizeof s) "\n"
        put(s,0,0)
        print "=> " (sizeof s) "\n"
        put(s,0,0)
        print "=> " (sizeof s) "\n"
        put(s,0,0)
        print "=> " (sizeof s) "\n"
        put(s,0,0)
        print "=> " (sizeof s) "\n"
        delete s

This does not cause an error, but always answer zero.

SystemAdmin - Fri Nov 18 12:52:36 EST 2011

Re: Getting the element count in a skip list
OurGuest - Fri Nov 18 13:01:27 EST 2011

The help file says sizeof is for arrays.

Re: Getting the element count in a skip list
SystemAdmin - Fri Nov 18 15:02:55 EST 2011

The Skip object does not track its element count natively. If you what the know the count you would have to track it yourself every time you successfully add/delete an element or do a quick iteration through it to calculate the size.

int sizeOfAnySkip = 0;
int anyData;
for anyData in mySkipList do {
    sizeOfAnySkip++;
}

Re: Getting the element count in a skip list
Mathias Mamsch - Fri Nov 18 18:22:50 EST 2011

Skip lists indeed do not keep track of their element count. Therefore iterating over them is the only solution. Regards, Mathias

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

Re: Getting the element count in a skip list
SystemAdmin - Mon Nov 21 03:00:12 EST 2011

Mathias Mamsch - Fri Nov 18 18:22:50 EST 2011
Skip lists indeed do not keep track of their element count. Therefore iterating over them is the only solution. Regards, Mathias

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

Thanks,

This is what I feared... Well, probably the simplest is to count every time I put a new element, or delete an existing element.

VBR,
Vincent.

Re: Getting the element count in a skip list
Helko - Mon Nov 21 10:04:48 EST 2011

SystemAdmin - Mon Nov 21 03:00:12 EST 2011
Thanks,

This is what I feared... Well, probably the simplest is to count every time I put a new element, or delete an existing element.

VBR,
Vincent.

Hi,

always ehan I use an Array or a Skip list, I have an element included which I use as a counter for the numbers of elements inside.

Thus each time I'm using Array, the position 0 is reserved for the counter value.
Code Pattern for this:

Array arr = create(1,10);

//add element
int i = 0;
for x in y do {
put(arr, 0, 0, ++i);
put(arr, 0, i, valOf(x));
}

//read elements
int nrOfArrElements = get(arr, 0, 0);
//print "nrOfArrElements : " nrOfArrElements "\n";
if (nrOfArrElements >0)
{
int loopCounter;
for loopCounter in 1 : nrOfArrElements do
{
TypeOfValue Value = (TypeCasting) get(arr, 0, loopCounter)
}
}
Cheers, Helko

Re: Getting the element count in a skip list
llandale - Mon Nov 21 15:45:28 EST 2011

SystemAdmin - Mon Nov 21 03:00:12 EST 2011
Thanks,

This is what I feared... Well, probably the simplest is to count every time I put a new element, or delete an existing element.

VBR,
Vincent.

It seems "easier" to just count it when you need to:

int  CountSkip(Skip in_skp)
{   int Count = 0
    string Data
    for Data in in_skp do
    {  Count++
    }
    return(Count)
}   // end CountSkip()
...
if (CountSkip(skpWhatever) > Threshold) then...

Maybe we could time how long it takes to count a Skip with 100,000 entries, but I think its real fast.

If you keep a running count you need to be careful about accounting for duplicate "puts" and empty "deletes".
{code}
put(skp, "A", "A"); Count++
put(skp, "A", "B"); Count++
Count is 2 but there is only one element in the Skip

Louie

Re: Getting the element count in a skip list
SystemAdmin - Tue Nov 22 11:29:13 EST 2011

llandale - Mon Nov 21 15:45:28 EST 2011

It seems "easier" to just count it when you need to:

int  CountSkip(Skip in_skp)
{   int Count = 0
    string Data
    for Data in in_skp do
    {  Count++
    }
    return(Count)
}   // end CountSkip()
...
if (CountSkip(skpWhatever) > Threshold) then...

Louie

Thank you Louie and al. for the additional information.

Actually what I was trying to do is to use a Skip as some sort of stack. So the key is just the depth and duplicates are not possible.

Maybe Skip are not the best type for stacks, I was thinking that a good old underlying Array would make it with some mechanism to relocate it when the sizes grows beyond the allocation.

Anyhow that would means building my own use type "Stack", which might be a better approach for futureproofness.
Vincent.

Re: Getting the element count in a skip list
llandale - Tue Nov 22 15:08:11 EST 2011

SystemAdmin - Tue Nov 22 11:29:13 EST 2011
Thank you Louie and al. for the additional information.

Actually what I was trying to do is to use a Skip as some sort of stack. So the key is just the depth and duplicates are not possible.

Maybe Skip are not the best type for stacks, I was thinking that a good old underlying Array would make it with some mechanism to relocate it when the sizes grows beyond the allocation.

Anyhow that would means building my own use type "Stack", which might be a better approach for futureproofness.
Vincent.

Skip skpStack = create()
int  StackPointer = 0
 
void  Push(string Value)
{  put(skpStack, ++StackPointer, Value)
}
 
string Pop()
{  string Value = ""
   if (find(skpStack, StackPointer, Value)) StackPointer--
   else Value = "" // Empty stack or error
   return(Value)
}
Push("B")
Push("C")
Push("A")
Push("C")
Pop
string Value
int Position = 0
for Value in skpStack do
{  Position = (int key skpStack)
   print Position "\t" Value "\n"
}
print StackPoint "\tStackOK = " (StackPointer == Position) "\n"

Louie